home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 November / EnigmA AMIGA RUN 02 (1995)(G.R. Edizioni)(IT)[!][issue 1995-11][Skylink CD].iso / earcd / util / misc / gadmget2.lha / GadMget / GadMGet.source.lha / tree.c < prev    next >
C/C++ Source or Header  |  1995-07-25  |  11KB  |  564 lines
  1. /* as_tree - tree library for as
  2.  * vix 14dec85 [written]
  3.  * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
  4.  * vix 06feb86 [added tree_mung()]
  5.  * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
  6.  * vix 23jun86 [added delete uar to add for replaced nodes]
  7.  */
  8.  
  9.  
  10. /* This program text was created by Paul Vixie using examples from the book:
  11.  * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
  12.  * 0-13-022005-1.  This code and associated documentation is hereby placed
  13.  * in the public domain.
  14.  */
  15.  
  16.  
  17. /*#define        DEBUG    "tree"*/
  18.  
  19.  
  20. #include <stdio.h>
  21. #include <exec/types.h>
  22. #include "vixie.h"
  23. #include "tree.h"
  24.  
  25. #ifndef MEMPOOLS_H
  26. #include <clib/exec_protos.h>
  27. #include <exec/memory.h>
  28. #endif
  29.  
  30. #ifdef DEBUG
  31. #define        MSG(msg)    printf("DEBUG: '%s'\n", msg);
  32. #else
  33. #define        MSG(msg)
  34. #endif
  35.  
  36. LONG lTreeTicker;
  37. LONG lTreeSubTicker;
  38. extern struct Window *mgetWnd;
  39. char *sTreeWriteHere;
  40. char *szTickerString;
  41.  
  42. void tree_init(ppr_tree)
  43. tree    **ppr_tree;
  44. {
  45.     ENTER("tree_init")
  46.     *ppr_tree = NULL;
  47.     EXITV
  48. }
  49.     
  50.  
  51. char *tree_srch(ppr_tree, pfi_compare, pc_user)
  52. tree    **ppr_tree;
  53. int    (*pfi_compare)();
  54. char    *pc_user;
  55. {
  56.     register int    i_comp;
  57.     /* register tree    *pr_new;  THIS VARIABLE NOT USED -- Jeremy */
  58.  
  59.     ENTER("tree_srch")
  60.  
  61.     if (*ppr_tree)
  62.     {
  63.         i_comp = (*pfi_compare)(pc_user, (**ppr_tree).tree_p);
  64.         if (i_comp > 0)
  65.             EXIT(tree_srch(
  66.                 &(**ppr_tree).tree_r,
  67.                 pfi_compare,
  68.                 pc_user
  69.             ))
  70.         if (i_comp < 0)
  71.             EXIT(tree_srch(
  72.                 &(**ppr_tree).tree_l,
  73.                 pfi_compare,
  74.                 pc_user
  75.             ))
  76.  
  77.         /* not higher, not lower... this must be the one.
  78.          */
  79.         EXIT((**ppr_tree).tree_p)
  80.     }
  81.  
  82.     /* grounded. NOT found.
  83.      */
  84.     EXIT(NULL)
  85. }
  86.  
  87.  
  88. void tree_add(ppr_tree, pfi_compare, pc_user, pfi_delete)
  89. tree    **ppr_tree;
  90. int    (*pfi_compare)();
  91. char    *pc_user;
  92. int    (*pfi_delete)();
  93. {
  94.     void    sprout();
  95.     int    i_balance = FALSE;
  96.  
  97.     if ((lTreeSubTicker >= 100)&&(mgetWnd != NULL)) 
  98.     {
  99.         sprintf(sTreeWriteHere,"%i",lTreeTicker);
  100.         SetWindowTitles(mgetWnd, szTickerString, (char *) ~0); 
  101.         lTreeSubTicker = 0;
  102.         lTreeTicker++;
  103.     }
  104.     
  105.     lTreeSubTicker++;
  106.     
  107.     ENTER("tree_add")
  108.     sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete);
  109.     EXITV
  110. }
  111.  
  112.  
  113. static void sprout(ppr, pc_data, pi_balance, pfi_compare, pfi_delete)
  114. tree    **ppr;
  115. char    *pc_data;
  116. int    *pi_balance;
  117. int    (*pfi_compare)();
  118. int    (*pfi_delete)();
  119. {
  120.     tree    *p1, *p2;
  121.     int    cmp;
  122.  
  123.     ENTER("sprout")
  124.  
  125.     /* are we grounded?  if so, add the node "here" and set the rebalance
  126.      * flag, then exit.
  127.      */
  128.     if (!*ppr) {
  129.         MSG("grounded. adding new node, setting h=true")
  130.         #ifdef MEMPOOLS_H
  131.         *ppr = (tree *) malloc(sizeof(tree));
  132.         #else
  133.         *ppr = (tree *) AllocMem(sizeof(tree),MEMF_ANY);
  134.         #endif
  135.         
  136.         (*ppr)->tree_l = NULL;
  137.         (*ppr)->tree_r = NULL;
  138.         (*ppr)->tree_b = 0;
  139.         (*ppr)->tree_p = pc_data;
  140.         *pi_balance = TRUE;
  141.         EXITV
  142.     }
  143.  
  144.     /* compare the data using routine passed by caller.
  145.      */
  146.     cmp = (*pfi_compare)(pc_data, (*ppr)->tree_p);
  147.  
  148.     /* if LESS, prepare to move to the left.
  149.      */
  150.     if (cmp < 0) {
  151.         MSG("LESS. sprouting left.")
  152.         sprout(&(*ppr)->tree_l, pc_data, pi_balance,
  153.             pfi_compare, pfi_delete);
  154.         if (*pi_balance) {    /* left branch has grown longer */
  155.             MSG("LESS: left branch has grown")
  156.             switch ((*ppr)->tree_b)
  157.             {
  158.             case 1:    /* right branch WAS longer; balance is ok now */
  159.                 MSG("LESS: case 1.. balnce restored implicitly")
  160.                 (*ppr)->tree_b = 0;
  161.                 *pi_balance = FALSE;
  162.                 break;
  163.             case 0:    /* balance WAS okay; now left branch longer */
  164.                 MSG("LESS: case 0.. balnce bad but still ok")
  165.                 (*ppr)->tree_b = -1;
  166.                 break;
  167.             case -1:
  168.                 /* left branch was already too long. rebalnce */
  169.                 MSG("LESS: case -1: rebalancing")
  170.                 p1 = (*ppr)->tree_l;
  171.                 if (p1->tree_b == -1) {    /* LL */
  172.                     MSG("LESS: single LL")
  173.                     (*ppr)->tree_l = p1->tree_r;
  174.                     p1->tree_r = *ppr;
  175.                     (*ppr)->tree_b = 0;
  176.                     *ppr = p1;
  177.                 }
  178.                 else {            /* double LR */
  179.                     MSG("LESS: double LR")
  180.  
  181.                     p2 = p1->tree_r;
  182.                     p1->tree_r = p2->tree_l;
  183.                     p2->tree_l = p1;
  184.  
  185.                     (*ppr)->tree_l = p2->tree_r;
  186.                     p2->tree_r = *ppr;
  187.  
  188.                     if (p2->tree_b == -1)
  189.                         (*ppr)->tree_b = 1;
  190.                     else
  191.                         (*ppr)->tree_b = 0;
  192.  
  193.                     if (p2->tree_b == 1)
  194.                         p1->tree_b = -1;
  195.                     else
  196.                         p1->tree_b = 0;
  197.                     *ppr = p2;
  198.                 } /*else*/
  199.                 (*ppr)->tree_b = 0;
  200.                 *pi_balance = FALSE;
  201.             } /*switch*/
  202.         } /*if*/
  203.         EXITV
  204.     } /*if*/
  205.  
  206.     /* if MORE, prepare to move to the right.
  207.      */
  208.     if (cmp > 0) {
  209.         MSG("MORE: sprouting to the right")
  210.         sprout(&(*ppr)->tree_r, pc_data, pi_balance,
  211.             pfi_compare, pfi_delete);
  212.         if (*pi_balance) {    /* right branch has grown longer */
  213.             MSG("MORE: right branch has grown")
  214.  
  215.             switch ((*ppr)->tree_b)
  216.             {
  217.             case -1:MSG("MORE: balance was off, fixed implicitly")
  218.                 (*ppr)->tree_b = 0;
  219.                 *pi_balance = FALSE;
  220.                 break;
  221.             case 0:    MSG("MORE: balance was okay, now off but ok")
  222.                 (*ppr)->tree_b = 1;
  223.                 break;
  224.             case 1:    MSG("MORE: balance was off, need to rebalance")
  225.                 p1 = (*ppr)->tree_r;
  226.                 if (p1->tree_b == 1) {    /* RR */
  227.                     MSG("MORE: single RR")
  228.                     (*ppr)->tree_r = p1->tree_l;
  229.                     p1->tree_l = *ppr;
  230.                     (*ppr)->tree_b = 0;
  231.                     *ppr = p1;
  232.                 }
  233.                 else {            /* double RL */
  234.                     MSG("MORE: double RL")
  235.  
  236.                     p2 = p1->tree_l;
  237.                     p1->tree_l = p2->tree_r;
  238.                     p2->tree_r = p1;
  239.  
  240.                     (*ppr)->tree_r = p2->tree_l;
  241.                     p2->tree_l = *ppr;
  242.  
  243.                     if (p2->tree_b == 1)
  244.                         (*ppr)->tree_b = -1;
  245.                     else
  246.                         (*ppr)->tree_b = 0;
  247.  
  248.                     if (p2->tree_b == -1)
  249.                         p1->tree_b = 1;
  250.                     else
  251.                         p1->tree_b = 0;
  252.  
  253.                     *ppr = p2;
  254.                 } /*else*/
  255.                 (*ppr)->tree_b = 0;
  256.                 *pi_balance = FALSE;
  257.             } /*switch*/
  258.         } /*if*/
  259.         EXITV
  260.     } /*if*/
  261.  
  262.     /* not less, not more: this is the same key!  replace...
  263.      */
  264.     MSG("I found it!  Replacing data value")
  265.     *pi_balance = FALSE;
  266.     if (pfi_delete)
  267.         (*pfi_delete)((*ppr)->tree_p);
  268.     (*ppr)->tree_p = pc_data;
  269.     EXITV
  270. }
  271.  
  272.  
  273. int tree_delete(ppr_p, pfi_compare, pc_user, pfi_uar)
  274. tree    **ppr_p;
  275. int    (*pfi_compare)();
  276. char    *pc_user;
  277. int    (*pfi_uar)();
  278. {
  279.     int    i_balance = FALSE, i_uar_called = FALSE;
  280.  
  281.     ENTER("tree_delete");
  282.     EXIT(delete(ppr_p, pfi_compare, pc_user, pfi_uar,
  283.                 &i_balance, &i_uar_called))
  284. }
  285.  
  286.  
  287. static int delete(ppr_p, pfi_compare, pc_user, pfi_uar,
  288.                         pi_balance, pi_uar_called)
  289. tree    **ppr_p;
  290. int    (*pfi_compare)();
  291. char    *pc_user;
  292. int    (*pfi_uar)();
  293. int    *pi_balance;
  294. int    *pi_uar_called;
  295. {
  296.     void    del(), balanceL(), balanceR();
  297.     tree    *pr_q;
  298.     int    i_comp, i_ret;
  299.  
  300.     ENTER("delete")
  301.  
  302.     if (*ppr_p == NULL) {
  303.         MSG("key not in tree")
  304.         EXIT(FALSE)
  305.     }
  306.  
  307.     i_comp = (*pfi_compare)((*ppr_p)->tree_p, pc_user);
  308.     if (i_comp > 0) {
  309.         MSG("too high - scan left")
  310.         i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, pc_user, pfi_uar,
  311.                         pi_balance, pi_uar_called);
  312.         if (*pi_balance)
  313.             balanceL(ppr_p, pi_balance);
  314.     }
  315.     else if (i_comp < 0) {
  316.         MSG("too low - scan right")
  317.         i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, pc_user, pfi_uar,
  318.                         pi_balance, pi_uar_called);
  319.         if (*pi_balance)
  320.             balanceR(ppr_p, pi_balance);
  321.     }
  322.     else {
  323.         MSG("equal")
  324.         pr_q = *ppr_p;
  325.         if (pr_q->tree_r == NULL) {
  326.             MSG("right subtree null")
  327.             *ppr_p = pr_q->tree_l;
  328.             *pi_balance = TRUE;
  329.         }
  330.         else if (pr_q->tree_l == NULL) {
  331.             MSG("right subtree non-null, left subtree null")
  332.             *ppr_p = pr_q->tree_r;
  333.             *pi_balance = TRUE;
  334.         }
  335.         else {
  336.             MSG("neither subtree null")
  337.             del(&pr_q->tree_l, pi_balance, &pr_q, pfi_uar,
  338.                                 pi_uar_called);
  339.             if (*pi_balance)
  340.                 balanceL(ppr_p, pi_balance);
  341.         }
  342.         #ifdef MEMPOOLS_H
  343.         free(pr_q);
  344.         #else
  345.         FreeMem(pr_q, sizeof(tree));
  346.         #endif
  347.         
  348.         if (!*pi_uar_called && pfi_uar)
  349.             (*pfi_uar)(pr_q->tree_p);
  350.         i_ret = TRUE;
  351.     }
  352.     EXIT(i_ret)
  353. }
  354.  
  355.  
  356. static void del(ppr_r, pi_balance, ppr_q, pfi_uar, pi_uar_called)
  357. tree    **ppr_r;
  358. int    *pi_balance;
  359. tree    **ppr_q;
  360. int    (*pfi_uar)();
  361. int    *pi_uar_called;
  362. {
  363.     void    balanceR();
  364.  
  365.     ENTER("del")
  366.  
  367.     if ((*ppr_r)->tree_r != NULL) {
  368.         del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfi_uar,
  369.                                 pi_uar_called);
  370.         if (*pi_balance)
  371.             balanceR(ppr_r, pi_balance);
  372.     } else {
  373.         if (pfi_uar)
  374.             (*pfi_uar)((*ppr_q)->tree_p);
  375.         *pi_uar_called = TRUE;
  376.         (*ppr_q)->tree_p = (*ppr_r)->tree_p;
  377.         *ppr_q = *ppr_r;
  378.         *ppr_r = (*ppr_r)->tree_l;
  379.         *pi_balance = TRUE;
  380.     }
  381.  
  382.     EXITV
  383. }
  384.  
  385.  
  386. static void balanceL(ppr_p, pi_balance)
  387. tree    **ppr_p;
  388. int    *pi_balance;
  389. {
  390.     tree    *p1, *p2;
  391.     int    b1, b2;
  392.  
  393.     ENTER("balanceL")
  394.     MSG("left branch has shrunk")
  395.  
  396.     switch ((*ppr_p)->tree_b)
  397.     {
  398.     case -1: MSG("was imbalanced, fixed implicitly")
  399.         (*ppr_p)->tree_b = 0;
  400.         break;
  401.     case 0:    MSG("was okay, is now one off")
  402.         (*ppr_p)->tree_b = 1;
  403.         *pi_balance = FALSE;
  404.         break;
  405.     case 1:    MSG("was already off, this is too much")
  406.         p1 = (*ppr_p)->tree_r;
  407.         b1 = p1->tree_b;
  408.         if (b1 >= 0) {
  409.             MSG("single RR")
  410.             (*ppr_p)->tree_r = p1->tree_l;
  411.             p1->tree_l = *ppr_p;
  412.             if (b1 == 0) {
  413.                 MSG("b1 == 0")
  414.                 (*ppr_p)->tree_b = 1;
  415.                 p1->tree_b = -1;
  416.                 *pi_balance = FALSE;
  417.             } else {
  418.                 MSG("b1 != 0")
  419.                 (*ppr_p)->tree_b = 0;
  420.                 p1->tree_b = 0;
  421.             }
  422.             *ppr_p = p1;
  423.         } else {
  424.             MSG("double RL")
  425.             p2 = p1->tree_l;
  426.             b2 = p2->tree_b;
  427.             p1->tree_l = p2->tree_r;
  428.             p2->tree_r = p1;
  429.             (*ppr_p)->tree_r = p2->tree_l;
  430.             p2->tree_l = *ppr_p;
  431.             if (b2 == 1)
  432.                 (*ppr_p)->tree_b = -1;
  433.             else
  434.                 (*ppr_p)->tree_b = 0;
  435.             if (b2 == -1)
  436.                 p1->tree_b = 1;
  437.             else
  438.                 p1->tree_b = 0;
  439.             *ppr_p = p2;
  440.             p2->tree_b = 0;
  441.         }
  442.     }
  443.     EXITV
  444. }
  445.  
  446.  
  447. static void balanceR(ppr_p, pi_balance)
  448. tree    **ppr_p;
  449. int    *pi_balance;
  450. {
  451.     tree    *p1, *p2;
  452.     int    b1, b2;
  453.  
  454.     ENTER("balanceR")
  455.     MSG("right branch has shrunk")
  456.     switch ((*ppr_p)->tree_b)
  457.     {
  458.     case 1:    MSG("was imbalanced, fixed implicitly")
  459.         (*ppr_p)->tree_b = 0;
  460.         break;
  461.     case 0:    MSG("was okay, is now one off")
  462.         (*ppr_p)->tree_b = -1;
  463.         *pi_balance = FALSE;
  464.         break;
  465.     case -1: MSG("was already off, this is too much")
  466.         p1 = (*ppr_p)->tree_l;
  467.         b1 = p1->tree_b;
  468.         if (b1 <= 0) {
  469.             MSG("single LL")
  470.             (*ppr_p)->tree_l = p1->tree_r;
  471.             p1->tree_r = *ppr_p;
  472.             if (b1 == 0) {
  473.                 MSG("b1 == 0")
  474.                 (*ppr_p)->tree_b = -1;
  475.                 p1->tree_b = 1;
  476.                 *pi_balance = FALSE;
  477.             } else {
  478.                 MSG("b1 != 0")
  479.                 (*ppr_p)->tree_b = 0;
  480.                 p1->tree_b = 0;
  481.             }
  482.             *ppr_p = p1;
  483.         } else {
  484.             MSG("double LR")
  485.             p2 = p1->tree_r;
  486.             b2 = p2->tree_b;
  487.             p1->tree_r = p2->tree_l;
  488.             p2->tree_l = p1;
  489.             (*ppr_p)->tree_l = p2->tree_r;
  490.             p2->tree_r = *ppr_p;
  491.             if (b2 == -1)
  492.                 (*ppr_p)->tree_b = 1;
  493.             else
  494.                 (*ppr_p)->tree_b = 0;
  495.             if (b2 == 1)
  496.                 p1->tree_b = -1;
  497.             else
  498.                 p1->tree_b = 0;
  499.             *ppr_p = p2;
  500.             p2->tree_b = 0;
  501.         }
  502.     }
  503.     EXITV
  504. }
  505.  
  506.  
  507. int tree_trav(ppr_tree, pfi_uar)
  508. tree    **ppr_tree;
  509. int    (*pfi_uar)();
  510. {
  511.     ENTER("tree_trav")
  512.  
  513.     if (!*ppr_tree)
  514.         EXIT(TRUE)
  515.  
  516.     if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar))
  517.         EXIT(FALSE)
  518.     if (!(*pfi_uar)((**ppr_tree).tree_p))
  519.         EXIT(FALSE)
  520.     if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar))
  521.         EXIT(FALSE)
  522.         
  523.     if ((lTreeSubTicker >= 170)&&(mgetWnd != NULL)) 
  524.     {
  525.         sprintf(sTreeWriteHere,"%i",lTreeTicker);
  526.         SetWindowTitles(mgetWnd, szTickerString, (char *) ~0); 
  527.         lTreeSubTicker = 0;
  528.         lTreeTicker++;
  529.     }
  530.     lTreeSubTicker++;
  531.  
  532.     EXIT(TRUE)
  533. }
  534.  
  535.  
  536. void tree_mung(ppr_tree)
  537. tree    **ppr_tree;
  538. {
  539.     ENTER("tree_mung")
  540.     if (*ppr_tree)
  541.     {
  542.         tree_mung(&(**ppr_tree).tree_l);
  543.         tree_mung(&(**ppr_tree).tree_r);
  544.         
  545.         #ifdef MEMPOOLS_H
  546.         free(*ppr_tree);
  547.         #else
  548.         FreeMem(*ppr_tree,sizeof(tree));
  549.         #endif
  550.  
  551.             if ((lTreeSubTicker >= 100)&&(mgetWnd != NULL))
  552.                 {
  553.                     sprintf(sTreeWriteHere,"%i",lTreeTicker);
  554.                     SetWindowTitles(mgetWnd, szTickerString, (char *) ~0);
  555.                     lTreeSubTicker = 0;
  556.                     lTreeTicker++;
  557.                 }
  558.             lTreeSubTicker++;
  559.  
  560.         *ppr_tree = NULL;
  561.     }
  562.     EXITV
  563. }
  564.